class Trie {
    class trieNode{
        boolean isEnd=false;
        trieNode[] charTable=new trieNode[26];
    }

    public int getLoc(char tmpChar){
        return tmpChar-'a';
    }

    trieNode rootNode;
    /** Initialize your data structure here. */
    public Trie() {
        rootNode=new trieNode();
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        trieNode tmpNode=rootNode;
        for (int i = 0; i < word.length(); i++) {
            int charLoc=getLoc(word.charAt(i));
            if(tmpNode.charTable[charLoc]==null){
                tmpNode.charTable[charLoc]=new trieNode();
            }
            tmpNode=tmpNode.charTable[charLoc];
        }
        tmpNode.isEnd=true;
    }

    public trieNode travelFind(String str){
        trieNode tmpNode=rootNode;
        for (int i = 0; i < str.length(); i++) {
            int charLoc=getLoc(str.charAt(i));
            if(tmpNode.charTable[charLoc]==null){
                return null;
            }
            tmpNode=tmpNode.charTable[charLoc];
        }
        return tmpNode;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        trieNode resNode=travelFind(word);
        return resNode!=null&&resNode.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        trieNode resNode=travelFind(prefix);
        return resNode!=null;
    }
}
